\documentclass{ctexart}
\usepackage{graphicx} %插入图片的宏包
\usepackage{diagbox}
\usepackage{float} %设置图片浮动位置的宏包
\usepackage{subfigure}
\usepackage{amsmath}
\title{Numerical Analysis Ex5}
\date{10-12-2022}
\author{王惠恒 3200300395}
\usepackage{geometry}
 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 top=5mm,
 }
\begin{document}
\maketitle
\textbf{I}:A detailed proof of Theorem 5.7.\\
\textbf{Theorem 5.7}: The set \textbf{C}[a,b] of continuous functions over [a,b] is an inner-product space over C with its inner product as 
$$<u,v>:=\int_{a}^{b} \rho (t)u(t)\overline{v(t)} dt$$
where $\overline{v(t)}$ is the complex conjugate of $v(t)$ and the weight function $\rho(x) \in \textbf{C}[a,b]$ satisfies $\rho(x)>0$ for all $x \in [a,b]$.In addition, \textbf{C}[a,b] with 
$$||u||_2:=(\int_{a}^{b}\rho(t)|u(t)|^2 dt)^\frac{1}{2}$$
is a normed vector space over R\\
Proof:\\
Positivity: 
\begin{align*}
    \forall u \in \textbf{C}[a,b],<u,u>&=\int_{a}^{b} \rho(x)u(x)\overline{u(x)}dx\\
    &=\int_{a}^{b} \rho(x)|u(x)|^2 dx\\
    & \geq 0 \\
    <u,u>&=0 \Leftrightarrow \rho(x)|u(x)|^2 \Leftrightarrow u(x)=0 \>\>\>\>(\rho(x)>0)
\end{align*}
Linearity:
\begin{align*}
    \forall u,v,s \in \textbf{C}[a,b], \forall c \in C
    <c(u+v),s>&=\int_{a}^{b} [\rho(x)c(u(x)+v(x))\overline{s(x)}] dx\\
    &=c\int_{a}^{b}\rho(x)u(x)\overline{s(x)} dx+c\int_{a}^{b}\rho(x)v(x)\overline{s(x)} dx\\
    &=c<u,s>+c<v,s>
\end{align*}
Symmetricity:
\begin{align*}
    \forall u,v \in \textbf{C}[a,b]
    <u,v>&=\int_{a}^{b}\rho(x)u(x)\overline{v(x)} dx\\
    &=\overline{\int_{a}^{b}\overline{\rho(x)u(x)\overline{v(x)}}} dx\\
    &=\overline{\int_{a}^{b}\rho(x)\overline{u(x)}v(x)} dx\\
    &=\overline{<v,u>}
\end{align*}
For the second part of proof of normed vector:\\
Positivity:
\begin{align*}
    \forall u \in \textbf{C}[a,b],||u||_2&=(\int_{a}^{b}\rho(t)|u(t)|^2 dt)^\frac{1}{2} \geq 0\\
    ||u||_2&=0 \Leftrightarrow \rho(x)|u(x)|^2=0 \Leftrightarrow u=0\\
\end{align*}
Homogeneity:
\begin{align*}
    \forall c \in C,||cu||_2=(\int_{a}^{b}\rho(t)(c|u(t)|)^2 dt)^\frac{1}{2}=|c|||u||_2
\end{align*}
Triangle Inequality:
\begin{align*}
    \forall u,v \in \textbf{C}[a,b],||u+v||_2&=(\int_{a}^{b}\rho(t)|u(t)+v(t)|^2 dt)^\frac{1}{2}\\
    &=(\int_{a}^{b}\rho(t)|u(t)|^2 dt)^\frac{1}{2}+2(\int_{a}^{b}\rho(t)|u(t)v(t)| dt)^\frac{1}{2}+(\int_{a}^{b}\rho(t)|v(t)|^2 dt)^\frac{1}{2}\\
    & \leq (\int_{a}^{b}\rho(t)|u(t)|^2 dt)^\frac{1}{2} +(\int_{a}^{b}\rho(t)|v(t)|^2 dt)^\frac{1}{2}\\
    ||u+v||_2 & \leq ||u||_2+||v||_2
\end{align*}
\textbf{II}:(a)Given that Chebyshev polynomials of the first kind are $T_n(t)=\cos (n \arccos t)$,$\rho(x)=\frac{1}{\sqrt{1-x^2}}$.We need to prove for $n \in \textbf{N}$,they are orthogonal.Consider $m \neq n$,
\begin{align*}
    <T_n,T_{m}>&=\int_{-1}^{1} \rho(t)T_n(t)\overline{T_{m}(t)} dt\\
    &=\int_{-1}^{1}\frac{\cos(n \arccos t)\cos(m\arccos t)}{\sqrt{1-t^2}} dt\\
    &=\frac{1}{2}\int_{-1}^{1} \frac{\cos[(n+m)\arccos t]+cos[(n-m)\arccos t]}{\sqrt{1-t^2}} dt \\
    &=\frac{1}{2}\int_{\pi}^{2\pi}\cos[(n+m)u]+cos[(n-m)u] du\>\>\>\>(u=\sqrt{1-t^2})\\
    &=0
\end{align*}
Thus,we proved the orthogonality of Chebyshev polynomials.\\

(b)By the recursion of Chebyshev polynomials,we have
\begin{align*}
    T_0(x)&=1=u_1\\
    T_1(x)&=x=u_2\\
    T_2(x)&=2x^2-1=u_3
\end{align*}
Then we use the Gram-Schmidt process to normalize them:
\begin{align*}
    v_1&=1,\>\>\>\>||v_1||^2=\int_{-1}^{1} \frac{1}{\sqrt{1-x^2}} dx=\pi\\
    u_1^*&=\frac{1}{\sqrt{\pi}}\\
    v_2&=x-<x,\frac{1}{\sqrt{\pi}}>\frac{1}{\sqrt{\pi}}=x,\>\>\>\>||v_2||^2=\frac{\pi}{2}\\
    u_2^*&=\sqrt{\frac{2}{\pi}}x\\
    v_3&=2x^2-1-<2x^2-1,\frac{1}{\sqrt{\pi}}>\frac{1}{\sqrt{\pi}}\\
    &-<2x^2-1,\sqrt{\frac{2}{\pi}}x>\sqrt{\frac{2}{\pi}}x=2x^2-1,\>\>\>\>||v_3||^2=\frac{\pi}{2}\\
    u_3^*&=\sqrt{\frac{2}{\pi}}(2x^2-1)
\end{align*}
$u_1^*,u_2^*,u_3^*$ are the basis of the orthogonal system.\\

\textbf{III}:(a)Given that $y(x)=\sqrt{1-x^2}, \forall x \in [-1,1]$.The approximation function in Fourier expansion is quadratic polynomial $s(x)=a_0+a_1x+a_2x^2$,thus we take the basis be $(u_1^*,u_2^*,u_3^*)$.The weight function is $\rho(x)=\frac{1}{\sqrt{1-x^2}}$.\\
\begin{align*}
    u_1^*&=\frac{1}{\sqrt{\pi}},u_2^*=\sqrt{\frac{2}{\pi}}x,u_3^*=\sqrt{\frac{2}{\pi}}(2x^2-1)\\
    s&=<y,u_1^*>u_1^*+<y,u_2^*>u_2^*+<y,u_3^*>u_3^*\\
    s&=\frac{2}{\pi}+0-\frac{4}{3\pi}(2x^2-1)\\
    s&=\frac{10}{3\pi}-\frac{8}{3\pi}x^2
\end{align*}

(b)Given that $y(x)=\sqrt{1-x^2}, \forall x \in [-1,1]$.The approximation function in normal form is quadratic polynomial $s=a_0+a_1x+a_2x^2$,thus we take the basis be $(1,x,x^2)$.The weight function is $\rho(x)=\frac{1}{\sqrt{1-x^2}}$.
\begin{align*}
    G(1,x,x^2)&=
    \begin{pmatrix}
        <1,1>&<1,x>&<1,x^2>\\
        <x,1>&<x,x>&<x,x^2>\\
        <x^2,1>&<x^2,x>&<x^2,x^2>
    \end{pmatrix}
    =\begin{pmatrix}
    \pi&0&\frac{\pi}{2}\\
    0&\frac{\pi}{2}&0\\
    \frac{\pi}{2}&0&\frac{3\pi}{8}
    \end{pmatrix}
\end{align*}
\begin{align*}
    c&=
    \begin{pmatrix}
        <\sqrt{1-x^2},1>\\
        <\sqrt{1-x^2},x>\\
        <\sqrt{1-x^2},x^2>
    \end{pmatrix}
    =\begin{pmatrix}
        2\\
        0\\
        \frac{2}{3}
    \end{pmatrix}
\end{align*}
\begin{align*}
    G^Ta=c\\
    a=
    \begin{pmatrix}
        \frac{10}{3\pi}\\
        0\\
        -\frac{8}{3\pi}
    \end{pmatrix}
\end{align*}
Thus,the quadratic function is $s=\frac{10}{3\pi}-\frac{8}{3\pi}x^2$.\\

\textbf{IV}:(a)Given that $u_1=1,u_2=x,u_3=x^2,\rho(x)=1$.Then implement Gram-Schmidt process with
$$<u(t),v(t)>=\sum_{i=1}^{N} \rho(t_i)u(t_i)v(t_i)$$
\begin{align*}
    v_1&=1,||v_1||^2=12\\
    u_1^*&=\frac{1}{\sqrt{12}}\\
    v_2&=x-<x,\frac{1}{\sqrt{12}}>\frac{1}{\sqrt{12}}=x-\frac{13}{2},||v_2||^2=143\\
    u_2^*&=\frac{1}{\sqrt{143}}(x-\frac{13}{2})\\
    v_3&=x^2-<x^2,\frac{1}{\sqrt{12}}>\frac{1}{\sqrt{12}}-<x^2,\frac{1}{\sqrt{143}}(x-\frac{13}{2})>\frac{1}{\sqrt{143}}(x-\frac{13}{2})=x^2-\frac{325}{6}-13(x-\frac{13}{2})\\
    &=x^2-13x+\frac{91}{3}\\
    ||v_3||^2&=\frac{4004}{3}\\
    u_3^*&=\sqrt{\frac{3}{4004}}(x^2-13x+\frac{91}{3})\\
\end{align*}

(b)By Fourier expansion:
\begin{align*}
    u_1^*&=\frac{1}{\sqrt{12}},u_2^*=\frac{1}{\sqrt{143}}(x-\frac{13}{2}),u_3^*=\sqrt{\frac{3}{4004}}(x^2-13x+\frac{91}{3})\\
    \hat{\varphi}(x)&=<y,u_1^*>u_1^*+<y,u_2^*>u_2^*+<y,u_3^*>u_3^*\\
    &=\frac{1662}{\sqrt{12}}(\frac{1}{\sqrt{12}})+\frac{589}{\sqrt{143}}[\frac{1}{\sqrt{143}}(x-\frac{13}{2})]+12068\sqrt{\frac{3}{4004}}[\sqrt{\frac{3}{4004}}(x^2-13x+\frac{91}{3})]\\
    &=\frac{277}{2}+\frac{589}{143}(x-\frac{13}{2})+\frac{1293}{143}(x^2-13x+\frac{91}{3})\\
    &=\frac{1293}{143}x^2-\frac{16220}{143}x+386\\
    & \approx 9.04x^2-113.43x+386
\end{align*}
which is identical to the answer of Example 5.48.\\

(c)If $N$ and $x_i's$ are the same, but the values of $y_i's$ are different,the orthonormal basis can be reused while the normal equations cannot be reused.For the Fourier expansion, a summation takes part in the approximation with the orthonormal basis,but altering the values of $y_i's$ needs to repeat the calculation of linear equations (which particularly of $c$ in $G^Ta=c$).The advantage of using Fourier expansion obviously more improves the effectiveness than using normal equations. \\

\textbf{PROGRAMMING REPORT}:Embodied by Matlab\\
\textbf{A}:
\underline{Code(Using Gram matrix)}
\begin{verbatim}
function [a]=Grammatrix(x,y,n)
G=zeros(n,n);
a=zeros(n,1);
c=zeros(n,1);

for i=1:n
    for j=1:n
        G(i,j)=sum(x.^(i-1).*x.^(j-1));
    end
end
for i=1:n
    c(i,1)=sum(x.^(i-1).*y);
end
a=inv(G)*c;
end

Command:
x=[0,0.5,1,1.5,2,2.5,3,3.5,4,4.5,5,5.5,6,6.5,7,7.5,8,8.5,9,9.5,10];
y=[2.9,2.7,4.8,5.3,7.1,7.6,7.7,7.6,9.4,9.0,9.6,10,10.2,9.7,8.3,8.4,9,8.3,6.6,6.7,4.1];
a=Grammatrix(x,y,3);
\end{verbatim}
Result:a=(2.1757,2.6704,-0.2384)'.Thus,the approximation polynomial is
$$\varphi(x)=-0.2384x^2+2.6704x+2.1757$$\\
\textbf{B}:\underline{Code(QR decomposition)}
\begin{verbatim}
function [a]=BQR(x,y)
[~,n]=size(x);
A=zeros(n,3);
A(:,1)=ones(n,1);
A(:,2)=x';
A(:,3)=(x.*x)';
[Q,R]=qr(A);
b=Q'*y';
b=b(1:3);
R=R(1:3,1:3);
a=inv(R)*b;
end

Command:
x=[0,0.5,1,1.5,2,2.5,3,3.5,4,4.5,5,5.5,6,6.5,7,7.5,8,8.5,9,9.5,10];
y=[2.9,2.7,4.8,5.3,7.1,7.6,7.7,7.6,9.4,9.0,9.6,10,10.2,9.7,8.3,8.4,9,8.3,6.6,6.7,4.1];
a=BQR(x,y)
\end{verbatim}
Result:a=(2.1757,2.6704,-0.2384)'.Thus,the approximation polynomial is
$$\varphi(x)=-0.2384x^2+2.6704x+2.1757$$\\
From the calculation above, we have \\
G=\begin{pmatrix}
    21&105&717\\
    105&717&5513\\
    717&5513&45167
\end{pmatrix}\\
R=\begin{pmatrix}
    -4.5826&-22.9129&-156.5713\\
    0&13.8744&138.7444\\
    0&0&-37.4438
\end{pmatrix}\\
The condition number of G is $1.8981 \times 10^4$ (use the command cond(G,2))and the condition number of R is $1.3777 \times 10^2$(use the command cond(R,2)).
\end{document}